package 力扣.动态规划.线性DP;

public class 打家劫舍198 {


    /**
     * 正解
     * 定义 dp 数组用来存储最大的抢劫量，其中 dp[i] 表示抢到第 i 个住户时的最大抢劫量。
     * 由于不能抢劫邻近住户，如果抢劫了第 i -1 个住户，那么就不能再抢劫第 i 个住户，所以
     * 公式：dp[i]=max{ (dp[i-2]+num[i]) , (dp[i-1]) }
     */
    public static int rob2(int[] nums) {
        int pre1=0,pre2=0;
        for (int i = 0; i <nums.length ; i++) {
            //巧妙的将前两个下边进行了使用
            int pre3=Math.max(pre1+nums[i],pre2);
            pre1=pre2;
            pre2=pre3;
        }
        return pre2;
    }


    public static void main(String[] args) {
        int []nums={2,7,9,3,1};
        int []nums2={1,1};
        int []nums3={1,3,1,3,100};
        int rob = rob2(nums3);
        System.out.println(rob);
    }

    public int rob3(int[] nums) {
        if(nums == null || nums.length == 0){
            return 0;
        }
        final  int N = nums.length;
        if (N < 2){
            return nums[0];
        }
        nums[1] = Math.max(0,Math.max(nums[0],nums[1]));
        //边界条件
        for (int i = 2; i < N; i++) {
            nums[i] = Math.max(nums[i - 2] + nums[i],nums[i - 1]);
        }
        return nums[N - 1];
    }
}
